#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 滑动窗口
// 209.长度最小的子数组
/*
    思路：
        1、进窗口
        2、判断是否大于正整数target
            1、更新结果
            2、出窗口
*/
class Solution
{
public:
    int minSubArrayLen(int target, vector<int> &nums)
    {
        int len = INT_MAX, sum = 0;
        for (int left = 0, right = 0; right < nums.size(); right++)
        {
            sum += nums[right];   // 进窗口
            while (sum >= target) // 判断
            {
                len = min(right - left + 1, len); // 更新结果
                sum -= nums[left++];              // 出窗口
            }
        }
        return len == INT_MAX ? 0 : len;
    }
};
// 滑动窗口
// 3.无重复字符的最长字串
/*
    思路：
        1.进窗口(让字符进入哈希表)
        2.判断(窗口内出现重复字符)
            出窗口(从哈希表中删除该字符)
        3.更新结果
*/
class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        int left = 0, right = 0;
        int hash[128] = {0}, size = s.size();
        int ret = 0;

        while (right < size)
        {
            hash[s[right]]++;          // 进窗口
            while (hash[s[right]] > 1) // 判断：窗口内出现重复字符
            {
                hash[s[left++]]--; // 出窗口
            }
            ret = max(ret, right - left + 1); // 更新
            right++;
        }

        return ret;
    }
};
// 滑动窗口
// 1004. 最大连续1的个数III
// 基本思路同上
class Solution
{
public:
    int longestOnes(vector<int> &nums, int k)
    {
        int ret = 0;
        for (int left = 0, right = 0, zero = 0; right < nums.size(); right++)
        {
            // 进窗口
            if (nums[right] == 0)
                zero++;
            // 判断
            while (zero > k)
            {
                // 出窗口
                if (nums[left++] == 0)
                    zero--;
            }
            // 更新
            ret = max(ret, right - left + 1);
        }

        return ret;
    }
};
// 滑动窗口
// 1658. 将x减到0的最小操作数
// 采用正难则反的思想：正向解决难度较大，采用逆向思维
/*
    思路：
        将问题转换为：从nums中移除一个最长的子数组，使得剩余元素的和为x
        所以，得出最长子数组后，再用总长度减去最长子数组的长度便是最终结果
*/
class Solution
{
public:
    int minOperations(vector<int> &nums, int x)
    {
        // nums数组的和
        int sum = 0;
        for (int a : nums)
            sum += a;

        // 得出最长子数组的和
        // 以及判断最长子数组的和是否小于0
        // 如果小于0便得出数组减去x(此时是数组内的所有数据)小于0，直接返回-1即可
        int target = sum - x;
        if (target < 0)
            return -1;

        int ret = -1;
        for (int left = 0, right = 0, tmp = 0; right < nums.size(); right++)
        {
            // 进窗口
            tmp += nums[right];

            // 判断
            while (tmp > target)
                // 出窗口
                tmp -= nums[left++];

            // 更新结果
            if (tmp == target)
                ret = max(ret, right - left + 1);
        }

        return ret == -1 ? ret : nums.size() - ret;
    }
};
// 滑动窗口
// 904. 水果成蓝
/*
    思路：
        使用哈希表维护水果种类，使用滑动窗口调整组内数据
*/
class Solution
{
public:
    int totalFruit(vector<int> &fruits)
    {
        int left = 0, right = 0, ret = -1;

        // unordered_map<int, int> hash;       // 哈希表维护水果种类
        int kinds = 0;
        int hash[100001] = {0};

        for (; right < fruits.size(); right++)
        {
            // 进窗口
            if (hash[fruits[right]] == 0)
                kinds++;
            hash[fruits[right]]++;

            // 判断
            if (kinds > 2)
            {
                // 出窗口
                hash[fruits[left]]--;
                if (hash[fruits[left]] == 0)
                    kinds--;
                left++;
            }
            // 更新
            ret = max(ret, right - left + 1);
        }

        return ret;
    }
};
// 滑动窗口
// 438.找到字符串中所有字母异位词
class Solution
{
public:
    // 方法一：暴力解法
    /*
        思路：采用滑动窗口+哈希表
        最后逐一判断两张哈希表是否相等
    */

    // bool check(int pp[],int ss[])
    // {
    //     for(int i = 0;i < 26;i++)
    //     {
    //         if(pp[i] != ss[i])
    //             return false;
    //     }

    //     return true;
    // }
    // vector<int> findAnagrams(string s, string p) {
    //     int pp[26] = {0};
    //     int ss[26] = {0};
    //     for(auto str:p)
    //         pp[static_cast<int>(str)-97]++;

    //     vector<int> ret;
    //     for(int left = 0,right = 0;right < s.size();right++)
    //     {
    //         // 进窗口
    //         ss[static_cast<int>(s[right])-97]++;

    //         // 判断
    //         if(right-left+1 > p.size())
    //         {
    //             // 出窗口
    //             ss[static_cast<int>(s[left++])-97]--;
    //         }
    //         // 更新结果
    //         if (check(pp,ss) == true)
    //         {
    //             ret.push_back(left);
    //         }
    //     }

    //     return ret;
    // }

    // 方法二：在利用滑动窗口和哈希表的基础上，再利用count记录总字符串出现的子字符串的字符个数
    vector<int> findAnagrams(string s, string p)
    {
        int pp[26] = {0};
        int ss[26] = {0};
        for (auto str : p)
            pp[static_cast<int>(str) - 97]++;

        vector<int> ret;
        int count = 0;
        for (int left = 0, right = 0; right < s.size(); right++)
        {
            // 进窗口
            ss[static_cast<int>(s[right]) - 97]++;
            // 如果成立
            // 那么说明该字符在总字符串中的出现次数 <= 子字符串中的哈希表字母数
            // 这里是为了判断右窗口的字符串属于子字符串
            if (ss[static_cast<int>(s[right]) - 97] <= pp[static_cast<int>(s[right]) - 97])
                count++;

            // 判断
            if (right - left + 1 > p.size())
            {
                // 出窗口
                // 如果成立
                // 那么说明该字符在总字符串中的出现次数 <= 子字符串中的哈希表字母数
                // 这里是为了判断左窗口的字符串属于子字符串
                if (ss[static_cast<int>(s[left]) - 97] <= pp[static_cast<int>(s[left]) - 97])
                    count--;
                ss[static_cast<int>(s[left++]) - 97]--;
            }
            // 更新结果
            if (count == p.size())
                ret.push_back(left);
        }

        return ret;
    }
};
// 滑动窗口
// 30. 串联所有单词的子串
/*
    思路：
        两层循环：
            第一层执行words中单个字符串的长度，即更改每次遍历的起始位置
            第二层遍历总长度，每次+单个字符串的长度

        移动条件：
            right: 一直在右移(+len)
            left: 除非达到某种条件才会右移(+len)，例如：滑动窗口内的字符串长度大于要找的字符串
*/
class Solution
{
public:
    static vector<int> findSubstring(string s, vector<string> &words)
    {
        unordered_map<string, int> hashwords;
        // 保存words里单词的频次
        for (auto str : words)
            hashwords[str]++;

        int len = words[0].size(), size = words.size();
        vector<int> ret;

        for (int i = 0; i < len; i++)
        {
            // 维护窗口里的单词频次
            unordered_map<string, int> hashs;
            for (int left = i, right = i, count = 0; right + len <= s.size(); right += len)
            {
                // 进窗口并维护count，count记录字符串数组words中的字符串出现在字符串s中的个数
                string in = s.substr(right, len);
                hashs[in]++;
                if (hashwords.count(in) && hashs[in] <= hashwords[in])
                    count++;

                // 判断，len*size：words的长度总和
                if (right - left + len > len * size)
                {
                    // 出窗口并维护count
                    string out = s.substr(left, len);
                    if (hashwords.count(out) && hashs[out] <= hashwords[out])
                        count--;
                    hashs[out]--;
                    left += len;
                }
                // 更新结果，如果相等，说明字符串数组words中的字符串此时全部出现，便记录起始位置
                if (count == size)
                    ret.push_back(left);
            }
        }
        return ret;
    }
};
// 滑动窗口
// 最小覆盖字串
/*
    思路：利用count记录哈希表hashs符合哈希表hasht的部分数据
*/
class Solution
{
public:
    string minWindow(string s, string t)
    {
        int hasht[128] = {0};
        int kinds = 0;
        for (auto c : t)
        {
            if (hasht[static_cast<int>(c)]++ == 0)
                kinds++;
        }

        int hashs[128] = {0};
        int left = 0, right = 0, count = 0;
        int min = INT_MAX, res = -1;
        for (; right < s.size(); right++)
        {
            // 进窗口
            int in = static_cast<int>(s[right]);
            if (++hashs[in] == hasht[in])
                count++;

            // 判断条件
            while (count == kinds)
            {
                // 更新结果
                if (right - left + 1 < min)
                {
                    min = right - left + 1;
                    res = left;
                }
                // 出窗口
                int out = static_cast<int>(s[left++]);
                if (hashs[out]-- == hasht[out])
                    count--;
            }
        }
        return res == -1 ? "" : s.substr(res, min);
    }
};